This invention relates to an apparatus for executing an area set operation and, more particularly, to an apparatus for a set operation of three-dimensional object and its display, which is used in machine design, operational simulation of a numerically controlled machine, operational simulation of a robot, etc.
Further stated more specifically, the present invention relates to an apparatus or a method wherein data for defining a three-dimensional object are inputted, set operation on an object is executed when it is needed and the object is displayed, with its face hidden from an observer's view being eliminated. Further, in case of the operational simulation of a numerically controlled machine, the apparatus inputs data of a shape of raw material to be machined and data of a cutter shape, executes a set operation of differentials between the data of the raw material shape and the data of the cutter shape, and displays a shape after the raw material is machined.
At present, various set operation methods and displaying methods are known. Almost all of them have problems on operation speed because a huge amount of operation is necessary for detection of mutual interference of faces and elimination of hidden faces, which are necessary to execute the set operation and the display. There is an application field in which there is no problem on the operation speed, however, in the field in which operational images such as in the operational simulation are required, processing at a higher speed is required.
Of high speed processing methods, there are Quadtree which treats with a two-dimensional area, and Octree which treats with a three-dimensional area. These methods employ mathematically the same principle.
Quadtree is invented by Warnock as disclosed in U.S. Pat. No. 3,602,702, and Octree is what Hunter G. M. applied Quadtree's concept to a three-dimensional area (a thesis "Computer application and data mechanism effective for graphics" submitted by Princeton College, electronics, computer science course). Further, D. Meagher proposed a method of inputting shape data practically, and displaying, based on Octree's concept, disclosed in Japanese Patent Laid-Open 60-237578.
Further, Geoff Wyvill proposes a model in which Octree is extended to reduce an amount cf necessary data (A functional model for constructive solid geometry, The Visual Computer (1985) 1; 3-14; Space Division for Ray Tracing in CSG, IEEE CG & A (1986) April: 28-34). Still further, Ingrid Carlbom proposes a model in which Octree is expanded by another method (An Algorithm for Geometric Set Operations Using Cellular Subdivision Techniques, IEEE CG & A (1987) May: 44-55).
Quadtree method and Octree method have the following problems:
(a) A huge amount of data is necessary and make it practically impossible to process objects of complicated shape.
(b) The Octree can execute, at a high speed, display of images from several specific directions dependent on the coordinate system, however, processing of generation of two-dimensional images viewed from arbitrary directions can not be executed at a high speed.
(c) It is necessary to set in advance dissolution of data representing an object. In case of partial extension being executed later so as to extend beyond the initially set dissolution, many processes are necessary to be carried out again.
(d) When it is used in computer aided design, it is necessary to identify the corresponding point of the face of a three-dimensional object, and the corresponding part in input data, from a point on an image projected to display on a picture frame. In the Octree method, however, it is very difficult.
Further, the Wyvill's method reduces a little an amount of the necessary data, however, the amount is still huge, and can not be treated with practically. The Carlbom's method can treat with only a shape composed of planes.